The transfer and storage of “real-time” data involves ever increasing bandwidth as the uses of electronic information continue to increase. Increased use of real-time data requires maximum transfer rates with minimum data loss or processing errors. Accordingly, interest in data compression has increased, both with respect to “lossless” data compression (in which excess data redundancy is eliminated without data loss) and to “lossy” compression, which removes redundant data as well as data judged to be “insignificant” according to criteria specific to the application.
Although substantial progress has been made in the development of lossless compression techniques, the amount of lossless compression possible in many applications is limited. For image compression, for example, a maximum compression ratio of 3:1 or less is typically realized. Lossy data compression techniques, on the other hand, are capable of substantially greater compression ratios in applications involving time series representations of analog signals (such as speech or music) and two-dimensional arrays representing images (e.g., still image, motion video). Thus, in these applications, a portion of the data can be thrown away with acceptable degradation of the signal after reconstruction.
Image processing applications are particularly suitable for lossy data compression techniques, since in many cases the image data sets are large. Images involve considerable redundancy and can be successfully compressed, using techniques such as the discrete cosine transform (DCT) in accordance with the JPEG (Joint Photographic Experts Group) standard. Compression ratios better than 10:1 without perceptual loss, and 20:1 or better with tolerable losses, can be achieved using the JPEG DCT compression or other JPEG compression techniques. Image compression using the JPEG standard is well known. Details of the JPEG standard are described in International Telecommunication Union Recommendation T.81, which is hereby incorporated by reference in its entirety.
FIGS. 1A and 1B are block diagrams of a conventional JPEG encoder configuration 100. In general, a JPEG encoder 110 receives data packaged as a series of minimum coded units (MCUs) 120, 121, 122, 123, 124, 125, 126, 127. Each MCU is composed of four 8×8 blocks of pixel data in a 4:2:2 luminance/chrominance (YUV or YCbCr) color space. The composition of a MCU depends on the input image color format. As the human eye is more sensitive to luminance difference, the chrominance pixels are subsampled by 2:1 horizontally in YCbCr 4:2:2 format, and additionally subsampled by 2:1 vertically in YCbCr 4:2:0 format. Thus for every pair of blue chrominance (Cb) and red chrominance (Cr) pixels, there are two corresponding luminance (Y) pixels in YCbCr 4:2:2 format and four corresponding Y pixels in YCbCr 4:2:0 format. Therefore, each MCU is composed of two blocks of Y data (Y0 and Y1) and one block of Cb and one block of Cr in YCbCr 4:2:2 format and four blocks of Y data (Y0, Y1, Y2, and Y3) and one block of Cb and one block of Cr in YCbCr 4:2:0 format. Each block is composed of 8×8 pixels.
A JPEG encoder performs DCT transform, quantization and entropy encoding on each 8×8 block of the input image. The DC component of the DCT coefficients is differentially encoded. In differential encoding, previously encoded data is used as a prediction for the current to-be-encoded data, and the difference between the current data and the prediction is entropy encoded to further remove the redundancy among data thus to achieve higher compression ratio. The decoder needs to have all the previous data used as prediction available before it can decode the current data. More importantly, if an error, such as transmission error, occurs in the previous data, all data using those erroneous data as prediction will be corrupted. Therefore, resynchronization codes are introduced. The placement of resynchronization codes resets the prediction and fresh decoding can start after the resynchronization codes without any knowledge of previous data. Such resynchronization codes are called restart markers in JPEG. Restart markers are inserted by the encoder into a compressed bitstream periodically once per every predefined number of MCUs which is called restart interval. The restart markers is an input parameter to the JPEG encoder. In addition to isolation of data corruptions, restart markers also enable parallel encoding or decoding and provide some extend of random data access.
In the example shown in FIGS. 1A and 1B, the restart interval is 4, however, other restart intervals may be used. The MCUs are grouped into sets 140, 145 of four MCUs (e.g., set 140 includes MCUs 120-123; set 145 includes MCUs 124-127). Each MCU 120-127 is compressed by JPEG encoder 110 in the serial order in which the MCU 120-127 is received. FIG. 1A illustrates MCUs 120-127 before compression. FIG. 1B shows MCUs 120-123 already compressed, and MCUs 124-127 awaiting compression. Based on the position of the input data, the JPEG encoder 110 is able to identify the type of data (i.e., Y0, Y1, Cb, Cr) that is being compressed. The data is serialized and concatenated for each MCU in the set 140, 145, compressed according to the JPEG standard, padded with additional bits (if necessary to fill out byte space before any JPEG marker), and then output, for instance, to a memory (not shown), where all sets of compressed data may be recombined into entropy coded segments (ECSs). In the example shown, the MCU set 140 is compressed into an ECS 150. A restart marker 130 is inserted after ECS 150.
Such conventional JPEG encoder configurations 100 are limited in speed to the compression speed of the JPEG encoder 110, due to the serialized encoding of the entire stream of MCUs. This is insufficient for applications requiring a faster compression speed. Accordingly, there is a need and desire for a faster compression of data.